In signal and data processing, and particularly, in image processing, kernel filters are frequently applied to input data to produce enhanced output data. A kernel filter works by applying a function to every point in a set of data. Typically, a kernel fitter includes a kernel and a function defined on the kernel. The kernel, which is often a rectangular area of pixels in a 2D image, specifies the region of support for the function. The function is usually in the form of a matrix of filter coefficients. The coefficients of the matrix are the multiplication factors that determine the contribution of each point within the kernel to generate a response of the filter. After all the underlying input data have been multiplied by the filter coefficients, the response at the current point is determined by taking the sum of the products. By selecting different kernel functions, different types of filtering can be performed.
Filtering can be computationally demanding. Therefore, conventional approaches try to break down the original kernel into a convolution of smaller kernels using, for example, scale-scale representations, see P. Burt, “Fast filter transforms for image processing,” Computer Vision, Graphics and Image Processing, vol. 16, 20-51, 1981. For a given image, a linear scale-space representation is a family of derived signals defined by convolution of the signal with a Gaussian kernel by concurrently smoothing and sub-sampling the signal. In this way, computationally efficient methods can be obtained.
However, a large number of multiplications are needed to carry out all of the convolutions with a large set of kernels. Therefore, it is also possible to design a 2D filter kernel, and then decompose the filter into a sum of separable one dimensional filters or cascaded representations, see J. Crowley, R. Stern, “Fast computation of the difference of low-pass transform,” IEEE Trans. Pattern Anal. Machine Intell., vol. 6, 212-222, 1984, P. Heckbert, “Filtering by repeated integration,” ACM SIGGRAPH Computer Graphics, vol. 20:4, 315-321, 1986, and W. Wells, “Efficient synthesis of Gaussian filters by cascaded uniform filters,” IEEE Trans. Pattern Anal. Machine Intell., vol. 8:2, 234-239, 1986. This can be done by using either an eigenvalue expansion of the 2D kernel, or application of a singular value decomposition (SVD), see W. S, Lu, H. P. Wang, A. Antoniou, “Design of 2D FIR digital filters by using the singular value decomposition,” IEEE Trans. Circuits System, vol. 37, 35-36, 1990, incorporated herein by reference.
By taking advantage of the separability of 2D Gaussian functions, it is possible to decomposed an anisotropic or directionally dependent Gaussian kernel into a one-dimensional Gaussian filter followed by another filter in a non-orthogonal direction, J. M. Geusebroek, A. Smeulders, J. Weijer, “Fast anisotropic Gauss filtering,” IEEE Transaction on Image Processing, vol. 12:8, 2003. That method allows fast calculation of edge and ridge maps using convolution and recursive schemes.
A sum-box filter technique approximates a large kernel linear filter to a factor by the sum of the translated outputs of sum-box filters, J. Shen, W. Shen, S. Castan, T. Zhang, “Sum-box technique for fast linear filtering,” Signal Process., vol. 82:8, 1109-1126, 2002. That method does not require multiplications. The method uses analysis on scaled spline functions. Their method makes it possible to achieve convolution with a large filter kernel by additions only. Box technique can implement Gaussian filters with multiplications, but cannot be used with linear filters other than Gaussian filters.
Another method is based on a fuzzy domain enhancement method, and a recursive and separable low-pass filter, H. Tang, T. Zhuang, E. X. Wu, “Realizations of fast 2-D/3-D image filtering and enhancement,” IEEE Trans Medical Imaging, vol. 20:2, 32-40, 2001. They process each pixel independently and modify both dynamic range and local variations. That method is also only applicable to Gaussian functions.
One method solves non-linear partial differential equations based on an adaptively determined vector field specifying non-local application points, B. Fischl, E. L. Schwartz, “Adaptive non-local filtering: A fast alternative to anisotropic diffusion for image enhancement,” IEEE Trans. Pattern Anal. Machine Intell., vol. 21:1, 42-48, 1999. Their method speeds up image enhancement, but is not applicable to linear filters.
Many filtering methods use orientation estimation for adaptation of local spatial texture. That often implies a sampling of orientations by anisotropic filtering. For a linear orientation scale-space, the anisotropic Gaussian function is the best suited causal filter. Orientation analysis is often approached by a set of steerable anisotropic filters.
Freeman et al. describe conditions under which a filter can be tuned to a specific orientation by making a linear combination of basis filters, W. T. Freeman, E. H. Adelson, “The design and use of steerable filters,” IEEE Trans. Pattern Anal. Machine Intell., vol. 13, 891-906, 1991. According to their framework, no exact basis exists for rotating an anisotropic Gaussian.
A method for generating a finite basis, which approximates an anisotropic Gaussian function is described by P. Perona, “Steerable-scalable kernels for edge detection and junction analysis,” Image Vis. Comput., vol. 10, 663-672, 1992. However, the number of basis filters is large, and the basis filters are non-separable, requiring high computational performance.
There are other methods that use reconfigurable hardware, or processor adapted software to accelerate the filtering process. Graphic processing unit (GPU) implementations of image filtering methods are also available, especially for the computation of area sums using pyramid representations, J. Kruger, R. Westermann, “Linear algebra operators for GPU implementation of numerical algorithms,” ACM Transactions on Graphics, vol. 22:3, 908-916, 2003.
Another GPU-based filtering of images with cubic B-splines that exploits bilinear texture interpolations is described by C. Sigg, M. Hadwiger, “Fast third-order texture filtering,” Matt Pharr, editor, GPU Gems 2: Programming Techniques for High-Performance Graphics, 313-329, 2005. While that technique allows for random access to a texture image, it requires a considerably number of texture lookups per pixel.
Strengert et al. show that GPUs can implement pyramid methods based on bilinear texture interpolation, and describe three examples: zooming with bi-quadratic B-spline filtering, efficient image blurring of arbitrary blur width, and smooth interpolation of scattered pixel data, M. Strengert, M. Kraus, T. Ertl, “Pyramid Methods in GPU-Based Image Processing,” In Proc. 11th International Fall Workshop Vision, Modeling, and Visualization, 2006.
In summary, most fast filtering methods either strictly depend on the shape of the filter function, or provide minor computational improvements.